package main

import "fmt"

func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	// 定义一个dp[m][n]数组，dp[i][j]表示到第[i][j]点有多少路径
	// dp[i][j] = dp[i-1][j] + dp[i][j-1]
	// 初始值： dp[i][0] 和 dp[0][j] 都为1
	// 与62不一样的在于有障碍物，碰到障碍物算0
	m := len(obstacleGrid)
	if m <= 0 {
		return 0
	}
	n := len(obstacleGrid[0])
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	// 初始化第一列
	for i := range dp {
		if obstacleGrid[i][0] != 1 {
			dp[i][0] = 1
		} else {
			break
		}
	}

	// 初始化第一行
	for i := range dp[0] {
		if obstacleGrid[0][i] != 1 {
			dp[0][i] = 1
		} else {
			break
		}
	}

	for i := 1; i < m; i++ {
		for j := 0; j < n; j++ {
			if j == 0 {
				continue
			}
			if obstacleGrid[i][j] != 1 {
				dp[i][j] = dp[i-1][j] + dp[i][j-1]
			}
			fmt.Println("dp=", dp)

		}
	}
	return dp[m-1][n-1]
}

func main() {
	// arrary := [][]int{
	// 	[]int{0, 0, 0},
	// 	[]int{0, 1, 0},
	// 	[]int{0, 0, 0},
	// }
	arrary := [][]int{
		[]int{0, 1},
		[]int{0, 0},
		[]int{1, 0},
	}
	fmt.Println(uniquePathsWithObstacles(arrary))
}
